import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-210-课程表2
 * @date 2025/4/27 10:43
 */
public class Solution210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<>(); // 邻接表
        int[] indeg = new int[numCourses]; // 保存每个课程节点的入度

        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
            indeg[prerequisite[0]]++;
        }

        int visited = 0;
        int[] ans = new int[numCourses];
        int k = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indeg.length; i++) {
            // 将入度为0的课程节点入队列
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int preCourse = queue.poll();
            for (int v : edges.get(preCourse)) {
                if (--indeg[v] == 0) {
                    queue.offer(v);
                }
            }
            visited++;
            ans[k] = preCourse;
            k++;
        }

        return (visited == numCourses) ? ans : new int[0];
    }
}
